// https://www.lintcode.com/problem/valid-sudoku/description
// 389. 判断数独是否合法
// 请判定一个数独是否有效。

// 该数独可能只填充了部分数字，其中缺少的数字用 . 表示。

// 样例
// The following partially filed sudoku is valid.

// 说明
// There are just 3 rules to Sudoku.
// Each row must have the numbers 1-9 occuring just once.
// Each column must have the numbers 1-9 occuring just once.
// And the numbers 1-9 must occur just once in each of the 9 sub-boxes of the grid.

// 注意事项
// 一个合法的数独（仅部分填充）并不一定是可解的。我们仅需使填充的空格有效即可。



class Solution {
public:
    /**
     * @param board: the board
     * @return: whether the Sudoku is valid
     */
    bool check(char c, bool used[9]) {
        if (c == '.')
        {
            return true;
        }
        if (used[c - '1'])
        {
            return false;
        } 
        used[c - '1'] = true;
        return true;
    }
    
    bool isValidSudoku(vector<vector<char>> &board) {
        bool used_raw[9];
        bool used_column[9];
        bool used_square[9];
        memset(used_raw, false, 9);
        memset(used_column, false, 9);
        memset(used_square, false, 9);
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if (!check(board[i][j], used_raw) || !check(board[j][i], used_column) || 
                !check(board[i / 3 * 3 + j / 3][i % 3 * 3 + j % 3], used_square))
                {
                    return false;
                }
            }
            memset(used_raw, false, 9);
            memset(used_column, false, 9);
            memset(used_square, false, 9);
        }
        return true;
    }
};



// class Solution {
// public:
//     bool isValidSudoku(const vector<vector<char>>& board) {
//         bool used[9];
//         for (int i = 0; i < 9; ++i) {
//             fill(used, used + 9, false);
//             for (int j = 0; j < 9; ++j) // 检查行
//                 if (!check(board[i][j], used))
//                     return false;
//             fill(used, used + 9, false);
//             for (int j = 0; j < 9; ++j) // 检查列
//                 if (!check(board[j][i], used))
//                     return false;
//         }
//         for (int r = 0; r < 3; ++r) // 检查9 个子格子
//             for (int c = 0; c < 3; ++c) {
//                 fill(used, used + 9, false);
//                 for (int i = r * 3; i < r * 3 + 3; ++i)
//                     for (int j = c * 3; j < c * 3 + 3; ++j)
//                         if (!check(board[i][j], used))
//                             return false;
//             }
//         return true;
//     }
//     bool check(char ch, bool used[9]) {
//         if (ch == '.') return true;
//         if (used[ch - '1']) return false;
//         return used[ch - '1'] = true;
//     }
// };